'''
https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/description/
'''

from typing import List

class Solution:

        # i: 当前要搞第几位
        # free: 之前的决策是如何的
        #       True: 之前没有选择过数字 或 之前选了数字但是小于那个限制。     那么从这里开始，我可以随意选择数字
        #       False: 之前选了数字但是==那个限制。      从这里开始每一步都得至少 <=
        # fixed: 表示之前有没有选择数字
        #          True: 后边必须都得选
        #          False: 后边，可选可不选
    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:
        m = len(digits)
        str_n = str(n)
        len_n = len(str_n)

        def f(i, free, fixed):
            if i == len_n:
                return 1 if fixed else 0    # 之前至少的选过数字
            res = 0
            if not fixed:
                res += f(i+1, True, False)
            if free:
                res += m * f(i+1, True, True)
            else:
                cur = str_n[i]
                for digit in digits:
                    if digit < cur:
                        res += f(i+1, True, True)
                    elif digit == cur:
                        res += f(i+1, False, True)
                    else:
                        break
            return res
        return f(0, False, False)

digits = ["3","4","8"]
n = 4
print(Solution().atMostNGivenDigitSet(digits, n))



